Statement#

Suppose you are given an array, nums, containing positive integers. You need to find the length of the longest bitonic subsequence in this array. A bitonic subsequence can be of the following three types:

  • It can consist of numbers that are first increasing and then decreasing. For example, (2,6,9,3,2)(2, 6, 9, 3, 2).

  • It can consist of numbers that are only increasing (where the decreasing part at the end is empty). For example, (2,3,7,9)(2, 3, 7, 9).

  • It can consist of numbers that are only decreasing (where the increasing part at the start is empty). For example, (15,12,5,3,2,1)(15, 12, 5, 3, 2, 1).

Let’s say you have the following array:

  • [19,20,5,3,13][19, 20, 5, 3, 13]

The longest bitonic subsequence from this array is (19,20,5,3)(19, 20, 5, 3), and the length of this subsequence is 44.

Constraints:

  • 11\leq nums.length 900\leq 900
  • 11\leq nums[i] 104\leq 10^4

Examples#

No.

nums

length

1

[6, 5, 3, 7, 10, 1, 2]

4

2

[1, 4, 9, 2, 16, 20]

5

3

[34, 33, 30, 25, 22, 40, 18]

6

Try it yourself#

Implement your solution in the following playground.

Python
usercode > main.py
Input #1
Longest Bitonic Subsequence

Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.

Hint: Use dynamic programming and see the magic.

Solution#

We will first explore the naive recursive solution to this problem and then see how it can be improved using the Longest Common Substring dynamic programming pattern.

Naive approach#

A naive approach would be to generate combinations of all possible bitonic subsequences in the array and select the one with the maximum length.

For example, we have the following array:

nums: [5,11,7,10][5, 11, 7, 10]

To find the length of the longest bitonic subsequence, we try all possible combinations:

  • (5)(5), length = 11

  • (5,11)(5, 11), length = 22

  • (5,7)(5, 7), length = 22

  • (5,10)(5, 10), length = 22

  • (5,11,7)(5, 11, 7), length = 33

  • (5,11,10)(5, 11, 10), length = 33

  • (5,7,10)(5, 7, 10), length = 33

  • (11)(11), length = 11

  • (11,7)(11, 7), length = 22

  • (11,10)(11, 10), length = 22

  • (7)(7), length = 11

  • (7,10)(7, 10), length = 22

  • (10)(10), length = 11

We select the bitonic subsequence with length 33.

We will use a Boolean variable, is_decreasing, which will have the following properties:

  • It will be FALSE if we’re at the increasing part of the subsequence.

  • It will be TRUE if we’re at the decreasing part of the subsequence.

Here is how the algorithm works:

  • Base case: If we’ve passed the end of the array, we return 00.

  • If we’re at the first element, we have three choices:

    • Exclude the element from the subsequence by default.

    • Include the element in the subsequence and then take the maximum length of moving to either the increasing or decreasing part of the subsequence for the next element.

    • The maximum length of either, including or excluding the current element, is selected.

  • If is_decreasing is FALSE, we’re in the increasing part of the subsequence. We now have three choices:

    • Exclude the element from the subsequence by default.

    • If nums[curr] > nums[prev], the element can be included to make a valid increasing subsequence; so, we include it and take the maximum length of moving to either the increasing or decreasing part of the subsequence for the next element.

    • We select the maximum length of the subsequence from either including or excluding the element from the above computations.

  • Otherwise, if is_decreasing is TRUE, we’re in the decreasing part of the subsequence. We now have two choices:

    • Exclude the element from the subsequence by default.

    • If nums[curr] < nums[prev], the element can be included to make a valid decreasing subsequence; so, we take the maximum of either, including or excluding the number.

Let’s implement the algorithm as discussed above:

Longest Bitonic Subsequence using recursion

Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.

Time complexity#

The time complexity of the naive approach is O(3n)O(3^n), where nn is the total number of elements in the array.

Space complexity#

As the maximum depth of the recursive call tree is nn, and each call stores its data on the stack, the space complexity of this approach is O(n)O(n).

Optimized solution using dynamic programming#

Now, let us improve the recursive solution using top-down and bottom-up approaches.

Top-down solution#

The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating redundant solutions over and over again by storing them in a table. In the recursive approach, the following three variables kept changing:

  • The current array index, curr.
  • The index of the last element in the subsequence, prev.
  • The boolean variable, is_decreasing, which indicated whether we were in the increasing or decreasing part of the subsequence.

We will use a 3-D table with the above three indexes to uniquely identify and store a subproblem. At any later time, if we encounter the same sub-problem, we can return the stored result from the table with an O(1)O(1) look-up instead of re-calculating that subproblem.

Let’s implement the algorithm as discussed above:

Longest Bitonic Subsequence using memoization

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we avoided redundant calculations by storing all the intermediate results in a 3-D table, the time complexity of this approach is reduced to O(n2)O(n^2), where nn is the number of elements in the array.

Space complexity#

We now need O(n2)O(n^2) space in memory to store intermediate values.

Bottom-up solution#

The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems.

For an array, nums, with length n, we do the following for every index, i.

  • We calculate the length of the longest increasing subsequence from nums[0]…nums[i].

  • We calculate the length of the longest increasing subsequence from nums[n - 1]…nums[i].

  • We add the two lengths and subtract them by 11 to get the length of the longest bitonic subsequence at nums[i].

The following illustration explains the above approach:

Created with Fabric.js 3.6.6 i = 0Length of the LIS from nums[0]..nums[i]: 1Length of the LIS from nums[n - 1]..nums[i]: 1Length of the LBS: 1 - 1 = 1We update the maximum length to 1.

1 of 9

Created with Fabric.js 3.6.6 i = 1Length of the LIS from nums[0]..nums[i]: 2Length of the LIS from nums[n - 1]..nums[i]: 5Length of the LBS: 2 + 5 - 1 = 6We update the maximum length to 6.

2 of 9

Created with Fabric.js 3.6.6 i = 2Length of the LIS from nums[0]..nums[i]: 2Length of the LIS from nums[n - 1]..nums[i]: 2Length of the LBS: 2 + 2 - 1 = 3Since 3 < 6, we do not update the maximum length.

3 of 9

Created with Fabric.js 3.6.6 i = 3Length of the LIS from nums[0]..nums[i]: 3Length of the LIS from nums[n - 1]..nums[i]: 4Length of the LBS: 3 + 4 - 1 = 6Since 6 == 6, we do not update the maximum length.

4 of 9

Created with Fabric.js 3.6.6 i = 4Length of the LIS from nums[0]..nums[i]: 3Length of the LIS from nums[n - 1]..nums[i]: 3Length of the LBS: 3 + 3 - 1 = 5Since 5 < 6, we do not update the maximum length.

5 of 9

Created with Fabric.js 3.6.6 i = 5Length of the LIS from nums[0]..nums[i]: 4Length of the LIS from nums[n - 1]..nums[i]: 3Length of the LBS: 4 + 3 - 1 = 6Since 6 == 6, we do not update the maximum length.

6 of 9

Created with Fabric.js 3.6.6 i = 6Length of the LIS from nums[0]..nums[i]: 2Length of the LIS from nums[n - 1]..nums[i]: 2Length of the LBS: 2 + 2 - 1 = 3Since 3 < 6, we do not update the maximum length.

7 of 9

Created with Fabric.js 3.6.6 i = 7Length of the LIS from nums[0]..nums[i]: 1Length of the LIS from nums[n - 1]..nums[i]: 1Length of the LBS: 1 + 1 - 1 = 1Since 1 < 6, we do not update the maximum length.

8 of 9

Created with Fabric.js 3.6.6 The maximum length of the bitonic subsequencein nums is 6.

9 of 9

We declare two 1-D arrays of length nn, which are initialized to 1s1s. They have the following properties:

  • lis_forward: This array contains the LIS from nums[0]…nums[i] for every ii in nums.

  • lis_backward: This array contains the LIS from nums[n - 1]…nums[i] for every ii in nums.

We fill the lis_forward array by traversing the nums array from left to right:

  • At each element of the array, nums[i], we use a nested loop to traverse all the elements, nums[j], that come before it:

    • For every nums[j], we check two conditions:

      • The first condition is nums[j] < nums[i], which checks if nums[j] can be included to make a valid increasing subsequence from nums[0]…nums[i]. If this condition is TRUE, we check the next condition. Otherwise, we skip this element by moving to the next iteration of the nested loop.

      • The second condition is 1 + lis_forward[j] > lis_forward[i] which checks if including nums[j] in the increasing subsequence from nums[0]…nums[i] will result in an increasing subsequence of a greater length than the existing subsequence length in list_forward[i]. If this condition is TRUE, we include nums[j] in the increasing subsequence by updating the value stored in lis_forward[i] to 1 + lis_forward[j]. Otherwise, we skip this element by moving to the next iteration of the nested loop.

We fill the lis_backward array by traversing the nums array from right to left:

  • At each element of the array, nums[i], we use a nested loop to traverse all the elements, nums[j], that come before it:

    • For every nums[j], we check two conditions:

      • The first condition is nums[j] < nums[i], which checks if nums[j] can be included to make a valid increasing subsequence from nums[n - 1]…nums[i]. If this condition is TRUE, we check the next condition. Otherwise, we skip this element by moving to the next iteration of the nested loop.

      • The second condition is 1 + lis_backward[j] > lis_backward[i] which checks if including nums[j] in the increasing subsequence from nums[n - 1]…nums[i] will result in an increasing subsequence of a greater length than the existing subsequence length in lis_backward[i]. If this condition is TRUE, we include nums[j] in the increasing subsequence by updating the value stored in lis_backward[i] to 1 + lis_backward[j]. Otherwise, we skip this element by moving to the next iteration of the nested loop.

We initialize a variable result, set to 11. This variable will be used to store the length of the longest bitonic subsequence in nums. We perform a final loop to simultaneously traverse the lis_forward and lis_backward arrays:

  • At each index, i, we will calculate the length of the longest bitonic subsequence till nums[i] through the formula: lis_forward[i] + lis_backward[i] - 1.
  • We store this value in a variable, length.
  • We set result to the max of the existing value of result and length.

When the loop ends, we return result.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 We will first fill the lis_forward table by traversing nums from left to right.

1 of 22

Created with Fabric.js 3.6.6

2 of 22

Created with Fabric.js 3.6.6 i = 1, j = 0condition 1: nums[i] > nums[j] , TRUEcondition 2: lis_forward[i] < 1 + lis_forward[j] , TRUESo lis_forward[i][j] = 1 + 1 = 2.

3 of 22

Created with Fabric.js 3.6.6 i = 1, j = 0condition 1: nums[i] > nums[j] , FALSE

4 of 22

Created with Fabric.js 3.6.6 i = 2, j = 0condition 1: nums[i] > nums[j] , TRUEcondition 2: lis_forward[i] < 1 + lis_forward[j] , TRUESo lis_first[i][j] = 1 + 1 = 2.

5 of 22

Created with Fabric.js 3.6.6 i = 3, j = 0condition 1: nums[i] > nums[j] , TRUEcondition 2: lis_forward[i] < 1 + lis_forward[j] , TRUESo lis_forward[i][j] = 1 + 1 = 2.

6 of 22

Created with Fabric.js 3.6.6 i = 1, j = 0condition 1: nums[i] > nums[j] , FALSE

7 of 22

Created with Fabric.js 3.6.6 i = 3, j = 2condition 1: nums[i] > nums[j] , TRUEcondition 2: lis_forward[i] < 1 + lis_forward[j] , TRUESo lis_forward[i][j] = 1 + 1 = 2.

8 of 22

Created with Fabric.js 3.6.6 We will now fill the lis_backward table by traversingnums from right to left.

9 of 22

Created with Fabric.js 3.6.6

10 of 22

Created with Fabric.js 3.6.6 i = 2, j = 3condition 1: nums[i] > nums[j] , TRUE

11 of 22

Created with Fabric.js 3.6.6 i = 1, j = 3condition 1: nums[i] > nums[j] , TRUEcondition 2: lis_backward[i] < 1 + lis_backward[j] , TRUESo lis_backward[i][j] = 1 + 1 = 2.

12 of 22

Created with Fabric.js 3.6.6 i = 1, j = 2condition 1: nums[i] > nums[j] , TRUEcondition 2: lis_backward[i] < 1 + lis_backward[j] , FALSE

13 of 22

Created with Fabric.js 3.6.6 i = 0, j = 3condition 1: nums[i] > nums[j] , FALSE

14 of 22

Created with Fabric.js 3.6.6 i = 0, j = 2condition 1: nums[i] > nums[j] , FALSE

15 of 22

Created with Fabric.js 3.6.6 i = 0, j = 1condition 1: nums[i] > nums[j] , FALSE

16 of 22

Created with Fabric.js 3.6.6 We will now traverse both the arrays: lis_forward, and lis_backward to calculate the maximum lengthof the bitonic subsequence in nums.

17 of 22

Created with Fabric.js 3.6.6 i = 0length = lis_forward[i] + lis_backward[i] - 1 = 1Since 1 == 1, the value of result stays the same.

18 of 22

Created with Fabric.js 3.6.6 i = 1length = lis_forward[i] + lis_backward[i] - 1 = 3Since 3 > 1, the value of result is updated to 3.

19 of 22

Created with Fabric.js 3.6.6 i = 2length = lis_forward[i] + lis_backward[i] - 1 = 2Since 3 > 2, the value of result stays the same.

20 of 22

Created with Fabric.js 3.6.6 i = 3length = lis_forward[i] + lis_backward[i] - 1 = 3Since 3 == 3, the value of result stays the same.

21 of 22

Created with Fabric.js 3.6.6 The variable result now stores the length of the longest bitonic subsequence in nums, which is 3, so we return result.

22 of 22

Let’s implement the algorithm as discussed above:

Longest Bitonic Subsequence using tabulation

Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.

Time complexity#

As we’re using nested loops to populate the two 1-D arrays to store the results of sub-problems that would be used later on, therefore, the time complexity of this approach will be O(n2)O(n^2).

Space complexity#

We need O(n)O(n) space in memory to store the intermediate values.

Maximum Sum Increasing Subsequence

Longest Alternating Subsequence